package leetcode_1000;

import java.util.Arrays;

public class DeleteColumnsToMakeSortedII_955 {
	public static void main(String[] args) {
		DeleteColumnsToMakeSortedII_955 test = new DeleteColumnsToMakeSortedII_955();
		test.minDeletionSize(new String[] {"abc","acc","abc"});
	}
	
	
	public int minDeletionSize(String[] A) {
		int N = A.length;
        int W = A[0].length();
        int ans = 0;
        String[] cur = new String[N];//这是声明了同样数量的string
        for (int j = 0; j < W; ++j) {//遍历每个index
            String[] cur2 = Arrays.copyOf(cur, N);
            for (int i = 0; i < N; ++i)
                cur2[i] += A[i].charAt(j);
            if (isSorted(cur2))
                cur = cur2;
            else
                ans++;
        }
        return ans;
    }
	
	public boolean isSorted(String[] A) {
        for (int i = 0; i < A.length - 1; ++i)
            if (A[i].compareTo(A[i+1]) > 0)
                return false;

        return true;
    }
}
